package com.leet.sort;

import java.util.Arrays;


/**
 * 测试快速排序算法编写
 */
public class QuickSort {


    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] arr = new int[]{1, 2, 5, 2, 4, 9, 2, 3};
        quickSort.sort(arr, 0, arr.length - 1);
        Arrays.stream(arr).forEach(System.out::println);
    }

    private void sort(int []arr, int i, int j){
        int start = i, end = j;
        if(start >= end) return;
        int partication = (int) (start + ((end - start) * Math.random()));
        int par = arr[partication];
        while(start < end){
            while(end > 0 && arr[end] >= par){
                end --;
            }
            while(start < end && arr[start] <= par){
                start ++;
            }
            if(start <= end){
                swap(arr, start, end);
            }
        }
        arr[start] = par;
        // 从左侧第一个值开始开始跟这个partation做比对
        sort(arr, i, partication - 1);
        sort(arr, partication + 1, j);
    }

    private void swap(int[] arr, int partication, int end) {
        int temp = arr[partication];
        arr[partication] = arr[end];
        arr[end] = temp;
    }

}
